package com.lmh.graphdisease.utils.ACKMPTree;

import java.util.*;

/**
 * @author lmh
 * @desc
 * @date 2023/3/20
 */
public class ACTree {
    private Node rootNode;

    public ACTree(List<String> KeyWords){
        //初始树
        initTree(KeyWords);
        //构建失败挑战
        buildFailLink();
    }

    /**
     *@author lmh
     *@date 2023/3/20
     *@desc 初始树
     */
    private void initTree(List<String> KeyWords){
        rootNode = new Node();
        rootNode.setSubNodes(new HashMap<>());
        String[] strings;
        for (String s:KeyWords){
            strings = s.split("");
            buildKeyMap(strings);
        }
    }
    /**
     *@author lmh
     *@date 2023/3/20
     *@desc 构建指定字符传数组的节点
     */
    private void buildKeyMap(String[] strs){
        String s;
        Node curNode = rootNode;
        Node node;
        for (int i = 0;i<strs.length;i++){
            s = strs[i];
            if(curNode.containSubNode(s)){
                node = curNode.getSubNode(s);
            }else {
                node = new Node();
                node.setLevel( i + 1);
                curNode.addSubNode(s,node);
            }
            if(i == strs.length - 1){
                node.setTerminal(true);
            }
            curNode = node;
        }
    }

    /**
     *@author lmh
     *@date 2023/3/20
     *@desc 失败跳转
     */
    private void buildFailLink(){
        buildFirstLevelFailLink();
        buildOtherLevelFailLink();
    }

    /**
     *@author lmh
     *@date 2023/3/20
     *@desc 根节点的所有第一级子节点，失败后跳转根节点
     */
    private void buildFirstLevelFailLink(){
        Collection<Node> nodes = rootNode.getSubNodes().values();
        for (Node node:nodes){
            node.setFailNodeTo(rootNode);
        }
    }

    /**
     *@author lmh
     *@date 2023/3/20
     *@desc 根节点、第一级节点以外的所有节点，失败后跳转到其父节点的失败节点的对应节点
     */
    private void buildOtherLevelFailLink(){
        Queue<Node> queue = new LinkedList<>(rootNode.getSubNodes().values());
        Node node;
        while (!queue.isEmpty()){
            node = queue.remove();
            buildNodeFailLink(node,queue);
        }
    }

    /**
     *@author lmh
     *@date 2023/3/20
     *@desc 构建指定节点的下一层节点的失败跳转
     */
    private void buildNodeFailLink(Node node,Queue<Node> queue){
        if(node.getSubNodes() == null || node.getSubNodes().isEmpty() ) return;
        queue.addAll(node.getSubNodes().values());
        Node failNode = node.getFailNodeTo();
        Set<String> subNodeKeys = node.getSubNodes().keySet();
        Node subFailNode;
        for (String key:subNodeKeys){
            subFailNode = failNode;
            while (subFailNode != rootNode && !subFailNode.containSubNode(key)){
                subFailNode = subFailNode.getFailNodeTo();
            }
            subFailNode = subFailNode.getSubNode(key);
            if(subFailNode == null) {
                subFailNode = rootNode;
            }
            node.getSubNode(key).setFailNodeTo(subFailNode);
        }
    }


    public Node getRootNode() {
        return rootNode;
    }
}
